package 剑指II;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-02
 **/

public class Jz013二维子矩阵的和 {

    /**
     * 给定一个二维矩阵 matrix，以下类型的多个请求：
     * 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
     * 实现 NumMatrix 类：
     * NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
     * int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、
     * 右下角 (row2, col2) 的子矩阵的元素总和。
     *  
     * 示例 1：
     * 输入:
     * ["NumMatrix","sumRegion","sumRegion","sumRegion"]
     * [[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
     * 输出:
     * [null, 8, 11, 12]
     * 解释:
     * NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]);
     * numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
     * numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
     * numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
     *  
     * 提示：
     * m == matrix.length
     * n == matrix[i].length
     * 1 <= m, n <= 200
     * -105 <= matrix[i][j] <= 105
     * 0 <= row1 <= row2 < m
     * 0 <= col1 <= col2 < n
     * 最多调用 104 次 sumRegion 方法
     */

    static class NumMatrix {

        /**
         * 我们定义 preSum[i][j]preSum[i][j] 表示 从 [0,0][0,0] 位置到 [i,j][i,j] 位置的子矩形所有元素之和。
         * 二维前缀和
         */
        private int[][] pre;
        private int[][] matrix;

        public NumMatrix(int[][] matrix) {
            this.matrix = matrix;
            this.pre = new int[matrix.length + 1][matrix[0].length + 1];
            for (int i = 1; i < this.pre.length; i++) {
                for (int j = 1; j < this.pre[i].length; j++) {
                    // 用笔在纸上写一下,可以得出
                    this.pre[i][j] = this.pre[i - 1][j] + this.pre[i][j - 1] - this.pre[i - 1][j - 1] + matrix[i - 1][j - 1];
                }
            }

        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            int sum = this.pre[row2 + 1][col2 + 1]
                    - this.pre[row2 + 1][col1]
                    - this.pre[row1][col2 + 1]
                    + this.pre[row1][col1];
            return sum;
        }
    }

    public static void main(String[] args) {
        int[][] arr = {{3, 0, 1, 4, 2}, {5, 6, 3, 2, 1}, {1, 2, 0, 1, 5}, {4, 1, 0, 1, 7}, {1, 0, 3, 0, 5}};
        NumMatrix numMatrix = new NumMatrix(arr);
        int result = numMatrix.sumRegion(1, 2, 2, 4);
        System.out.println(result);
    }

}
